package project2;

import java.util.*;
import java.io.PrintWriter;

/*********************************************************************
 * Implementation of the forward dynamic programming for MSA
 * all sqeuences have the same length - n
 * usign priority queue
 *********************************************************************/

public class FDP {

    private precomputation p;
    private PriorityQueue<Cell> pq = new PriorityQueue<Cell>();
    private int k, n, gap_cost;
    private int[][] score_matrix;
    private String[] seq;

    public int cost =0;
    public double time = 0;
    public int cells = 0;

    FDP(int[][] m, int g, String[] s, int i, int j,precomputation r) {
        p = r;
        score_matrix = m;
        gap_cost = g;
        seq = s;
        k = i;
        n = j;

    }

    public void run_upper_bound(PrintWriter out, int upper_bound) {
        //I compute binari[i] -  the binary representation of i+1
        String[] binary = new String[(int) java.lang.Math.pow(2,k)-1];
        for(int i=0; i<java.lang.Math.pow(2,k)-1; i++) {
            binary[i] = Integer.toBinaryString(i+1);
            for(int j=binary[i].length(); j<k; j++)
                    binary[i] = (new String("0")).concat(binary[i]);
        }
        //I keep track of how many cells I visited
        int how_many = 0;
        pq.add(new Cell(0,k,0));
        while(true) {
            Cell c = pq.poll();
            how_many++;
            //System.out.println();
            //System.out.println("-----------------");
            //System.out.println("I am at cell ");
            //c.print();
            if(c.compareTo(new Cell(0,k,n))==0) {
                cost = c.get_value();
                cells = how_many;
                break;
            }
            //for each succesor
            for(int i=0; i<java.lang.Math.pow(2,k)-1; i++) {
                //I have to construct succ - the ith succesor of c
                Cell succ = new Cell(c);
                boolean updated = false;
                for(int j=0; j<k; j++) {
                    //I want to update the coordinates in accordance with binary
                    if(binary[i].charAt(j)=='1')
                        if(succ.get_coord_at(j)<n) {
                            succ.modify_coord_at(j,1);
                            updated = true;
                        }
                }
                if(updated) {
                    //now succ is a succesor cell of c
                    int lower_bound = 0;
                    for(int u=0; u<k-1; u++)
                        for(int v=u+1; v<k; v++) {
                            lower_bound += p.get_score(u,v,succ.get_coord_at(u),succ.get_coord_at(v));
                        }
                    int costs = c.get_value()+ cost(c,succ);
                    succ.modify_value(costs);
                    //System.out.print(i+"th succesor: ");succ.print();
                    if(costs+lower_bound<=upper_bound) {
                        //System.out.println("it verifies the condition");
                        Iterator<Cell> it = pq.iterator();
                        if(it.hasNext()){
                            //System.out.println("I am going through the queue");
                            Cell aux = new Cell(0,k,0);
                            boolean seen = false;
                            while(it.hasNext()) {
                                aux = it.next();
                                //System.out.print("I look at ");aux.print();
                                if(succ.compareTo(aux)==0) {
                                    seen = true;
                                    break;
                                }
                            }
                            if(seen) {
                                //System.out.print("I already have this cell: ");aux.print();
                                if(aux.get_value()>costs) {
                                    //System.out.println("But I will update it's value with "+costs);
                                  pq.remove(aux);
                                  pq.add(succ);
                                }
                            }
                            else {
                                //System.out.println("I don't have it - I add it");
                                pq.add(succ);
                            }
                        }
                        else {
                            //System.out.println("The queue was empty");
                            pq.add(succ);
                        }
                    }
                }
            }
        }
    }

    private int value(char c){
        if(c=='a') return 0;
        if(c=='c') return 1;
        if(c=='g') return 2;
        if(c=='t') return 3;
        return -1;
    }

    private int cost(Cell c1, Cell c2) {
        int cost = 0;
        for(int i=0; i<k-1; i++)
            for(int j=i+1; j<k; j++) {
                //I add the cost of seq[i] and seq[j]
                if(c1.get_coord_at(i)!=c2.get_coord_at(i))
                    //I made a move in seq[i]
                    if(c1.get_coord_at(j)!=c2.get_coord_at(j)) {
                        //I made a move in seq[j] - I add the score of Match
                        cost += score_matrix[value(seq[i].charAt(c2.get_coord_at(i)-1))][value(seq[j].charAt(c2.get_coord_at(j)-1))];
                    }
                    else
                        //I didn't make a move in seq[j] - I add the gap cost
                        cost += gap_cost;
                else
                    //I didn't make a move in seq[i]
                    if(c1.get_coord_at(j)!=c2.get_coord_at(j))
                        //I made a move in seq[j] - I add the gap cost
                        cost += gap_cost;
            }
        return cost;
    }

}

